:- module(colgen).
:- reexport colgen_ except var_dual / 6, get_dual / 3, get_idx / 3, get_rhs / 3, set_dual / 3, bp_solve / 2, cg_solver_setup / 3, cg_solver_setup / 4, cg_integers / 2, add_cg_pool_constraint / 3, cg_eq / 3, cg_ge / 3, cg_le / 3, cg_sp_count / 2, cg_sp_sol / 2, cg_sp_rc_sum / 2, cg_minimize / 4, cg_minimize / 5, cg_var_get / 4, cg_get / 3.
:- comment(summary, "Column generation library").
:- comment(author, "Andrew Eremin").
:- comment(copyright, "Imperial College London and Parc Technologies").
:- comment(date, "$Date: 2003/12/11 21:09:57 $").
:- comment(status, prototype).
:- comment(desc, html("<P>\n\n   This library lets you use hybrid column generation. Partial linear\n   constraints are posted to a solver and further variables added to\n   them during search as they become profitable. The generated\n   variables will have a column of coefficients in the constraints of\n   the colgen instance associated with them corresponding to\n   particular instantiations of the variables of a subproblem. The\n   predicate to find profitable subproblem variable instantiations is\n   supplied by the user. When a user-defined branching predicate is\n   provided the library can also be sued for hybrid branch-and-price.\n</P><P>\n   The library uses the eplex library to solve LP master\n   problems, from which dual values are used to create cost functions\n   for the user-defined subproblem. Solution of master and subproblems\n   will iterate until no further subproblem solutions are posted to\n   the colgen instance.\n</P> ")).
:- comment($= / 2, [template : "ColgenInstance:(?X $= ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [$=< / 2, $>= / 2, (=:=) / 2, (=<) / 2, (>=) / 2, var_get / 3], summary : "Constrains X to be equal to Y.", desc : html("    <P>\n    Logically: Constrains X to be less than or equal to Y.  X and Y\n    are partial linear expressions. Partial linear expressions may\n    contain terms of the form <TT>implicit_sum(+Var)</TT> in addition\n    to any terms allowed within a standard linear\n    expression. Variables occurring inside <TT>implicit_sum/1</TT>\n    terms are taken to be subproblem variables whose instantiation\n    will correspond to the coefficient of a generated master problem\n    variable in this constraint. Operationally, the constraint gets\n    delayed until the external solver state for ColgenInstance is\n    invoked.\n    </P><P>\n    The $ version of the arithmetic constraints are provided to allow\n    code to be written which does not specify the solver. They are\n    equivalent to their colgen instance counterparts without the $\n    prefix.\n    </P>\n ")]).
:- comment($=< / 2, [template : "ColgenInstance:(?X $=< ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [$= / 2, $>= / 2, (=:=) / 2, (=<) / 2, (>=) / 2, var_get / 3], summary : "Constrains X to be less than or equal to Y.", desc : html("    <P>\n    Logically: Constrains X to be less than or equal to Y.  X and Y\n    are partial linear expressions. Partial linear expressions may\n    contain terms of the form <TT>implicit_sum(+Var)</TT> in addition\n    to any terms allowed within a standard linear\n    expression. Variables occurring inside <TT>implicit_sum/1</TT>\n    terms are taken to be subproblem variables whose instantiation\n    will correspond to the coefficient of a generated master problem\n    variable in this constraint. Operationally, the constraint gets\n    delayed until the external solver state for ColgenInstance is\n    invoked.\n    </P><P>\n    The $ version of the arithmetic constraints are provided to allow\n    code to be written which does not specify the solver. They are\n    equivalent to their colgen instance counterparts without the $\n    prefix.\n    </P>\n ")]).
:- comment($>= / 2, [template : "ColgenInstance:(?X $>= ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [$= / 2, $=< / 2, (=:=) / 2, (=<) / 2, (>=) / 2, var_get / 3], summary : "Constrains X to be greater than or equal to Y.", desc : html("    <P>\n    Logically: Constrains X to be greater than or equal to Y. X and Y\n    are partial linear expressions. Partial linear expressions may\n    contain terms of the form <TT>implicit_sum(+Var)</TT> in addition\n    to any terms allowed within a standard linear\n    expression. Variables occurring inside <TT>implicit_sum/1</TT>\n    terms are taken to be subproblem variables whose instantiation\n    will correspond to the coefficient of a generated master problem\n    variable in this constraint. Operationally, the constraint gets\n    delayed until the external solver state for ColgenInstance is\n    invoked.\n    </P><P>\n    The $ version of the arithmetic constraints are\n    provided to allow code to be written which does not specify the\n    solver. They are equivalent to their colgen instance counterparts\n    without the $ prefix.\n    </P>\n ")]).
:- comment((=:=) / 2, [template : "ColgenInstance:(?X =:= ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [(=<) / 2, (>=) / 2, $= / 2, $=< / 2, $>= / 2, var_get / 3], summary : "Constrains X to be equal to Y.", desc : html("\tLogically: Constrains X to be equal to Y. X and Y are partial\n\tlinear expressions. Partial linear expressions may contain\n\tterms of the form <TT>implicit_sum(+Var)</TT> in addition to\n\tany terms allowed within a standard linear\n\texpression. Variables occurring inside <TT>implicit_sum/1</TT>\n\tterms are taken to be subproblem variables whose instantiation\n\twill correspond to the coefficient of a generated master\n\tproblem variable in this constraint. Operationally, the\n\tconstraint gets delayed until the external solver state for\n\tColgenInstance is invoked.")]).
:- comment((=<) / 2, [template : "ColgenInstance:(?X =< ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [(=:=) / 2, (>=) / 2, $= / 2, $=< / 2, $>= / 2, var_get / 3], summary : "Constrains X to be less than or equal to Y.", desc : html("\tLogically: Constrains X to be less than or equal to Y. X and\n\tY are partial linear expressions. Partial linear expressions\n\tmay contain terms of the form <TT>implicit_sum(+Var)</TT> in\n\taddition to any terms allowed within a standard linear\n\texpression. Variables occurring inside <TT>implicit_sum/1</TT>\n\tterms are taken to be subproblem variables whose instantiation\n\twill correspond to the coefficient of a generated master\n\tproblem variable in this constraint. Operationally, the\n\tconstraint gets delayed until the external solver state for\n\tColgenInstance is invoked.")]).
:- comment((>=) / 2, [template : "ColgenInstance:(?X >= ?Y)", args : ["X" : "Partial linear expression", "Y" : "Partial linear expression"], see_also : [(=:=) / 2, (=<) / 2, $= / 2, $=< / 2, $>= / 2, var_get / 3], summary : "Constrains X to be greater than or equal to Y.", desc : html("\tLogically: Constrains X to be greater than or equal to Y. X\n\tand Y are partial linear expressions. Partial linear\n\texpressions may contain terms of the form\n\t<TT>implicit_sum(+Var)</TT> in addition to any terms allowed\n\twithin a standard linear expression. Variables occurring\n\tinside <TT>implicit_sum/1</TT> terms are taken to be\n\tsubproblem variables whose instantiation will correspond to\n\tthe coefficient of a generated master problem variable in this\n\tconstraint. Operationally, the constraint gets delayed until\n\tthe external solver state for ColgenInstance is invoked.")]).
:- comment(cg_subproblem_solution / 1, [template : "ColgenInstance:cg_subproblem_solution(++Value)", args : ["Value" : "Subproblem solution (sp_sol structure) or list of subproblem solutions"], summary : "Posts new subproblem solution(s) to the colgen instance ColgenInstance.", desc : html("  <P>\n  Post subproblem solution(s) corresponding to a column of coefficients\n  for a new master problem variable to the colgen instance\n  <TT>ColgenInstance</TT>. The argument must be a <TT>sp_sol</TT>\n  structure or list of such structures:\n <PRE>\n      sp_sol(cost, coeff_vars, aux)\n </PRE>\n  where <TT>cost</TT> is the master problem cost function coefficient\n  of the solution, <TT>coeff_vars</TT> is a list of <TT>Id-Val</TT>\n  pairs corresponding to the subproblem variable solution values and\n  identifier of the constraint in which it occurred as an implicit sum\n  term for those subproblem variables with a non-zero solution\n  value. <TT>aux</TT> should contain any problem specific information\n  which is of interest that is not represented uniquely by the cost\n  and objective coefficients.\n  </P>\n  ")]).
:- comment(colgen_instance / 1, [amode : colgen_instance(++), args : ["ColgenInstance" : "Colgen instance name (atom)"], summary : "Initialises the colgen instance ColgenInstance.", desc : html("  <P>\n  Initialises the colgen instance ColgenInstance. A colgen instance is an\n  instance of the colgen solver, to which colgen partial linear arithmetic\n  constraints can be posted, and to which an external LP solver can be\n  associated and used to optimise the posted constraints with respect\n  to some objective.\n  </P><P>\n  If ColgenInstance is not an already existing colgen instance, a new colgen\n  instance will be created and initialised. If it is an existing colgen\n  instance, and it is not currently being used (having no outstanding posted\n  constraints and no associated solver), it is effectively reinitialised.\n  Otherwise, the predicate aborts with an error. Note that a colgen instance\n  is a module, and each colgen instance can be associated with at most one\n  solver at any time and vice versa.\n  </P>\n  "), see_also : [(>=) / 2, (=:=) / 2, (=<) / 2, $>= / 2, $= / 2, $=< / 2, var_get / 3]]).
:- comment(get / 2, [template : "ColgenInstance:get(++What, -Value)", args : ["What" : "Specification for information wanted (atom)", "Value" : "Returned value of What"], summary : "Obtain global problem information.", desc : html("<P>\n   Retrieve information about solver constraints and results, for the\n   colgen instance ColgenInstance. What can take one of the following values:\n\n<DL>\n    <DT><TT>dual(+Id)</TT>\n      <DD>Returns the floating-point value of the\n      current dual value for the constraint having identifier Id. See\n      also <TT>sp_obj</TT> below.\n<P>\n    <DT><TT>sp_obj(+Id)</TT>\n      <DD>Returns the sub problem objective terms currently associated\n      associated with the constraint having identifier Id. This will\n      be a term <TT>Val*Var</TT> where Val is the current dual value\n      for the constraint as also returned by\n      <TT>ColgenInstance:get(dual(Id), Val)</TT> and Var is the\n      subproblem variable in the implicit sum term of the\n      constraint. It is the users responsibility to get all relevant\n      terms of the current cost function and ensure that subproblem\n      solutions posted to the colgen instance have a non-negative\n      cost.\n<P>\n    <DT><TT>vars</TT>\n      <DD>Returns a list of all variables currently\n      associated with the colgen instance <TT>ColgenInstance</TT>.\n<P>\n    <DT><TT>non_zero_vars</TT>\n      <DD>Returns a list of all variables currently associated with\n      the colgen instance <TT>ColgenInstance</TT> that have a non-zero\n      optimal solution. This may be more efficient than retrieving all\n      problem variables after solution, since very many variables can\n      be generated and most will have a zero value in the optimal\n      solution.\n<P>\n    <DT><TT>frac_vars</TT>\n      <DD>Returns a list of all variables currently associated with\n      the colgen instance <TT>ColgenInstance</TT> that have a\n      fractional optimal solution. This is intended for use primarily\n      in user-defined problem branching predicates.\n</DL>")]).
:- comment(identified_constraint / 2, [template : "ColgenInstance:identified_constraint(+Cstr, ?Id)", args : ["Cstr" : "colgen constraint"], summary : "Post an identified constraint to the colgen instance ColgenInstance.", desc : html("  <P>\n  Post a constraint to the colgen instance <TT>ColgenInstance</TT>\n  which will be associated with the identifier <TT>Id</TT>. The\n  constraint <TT>Cstr</TT> must be a valid colgen constraint of type\n  <TT>>=/2,=:=/2,=</2,$>=/2,$=/2,$=</2</TT>. If <TT>Id</TT> is\n  uninstantiated it will be unified with the external solver row\n  number of the constraint when this is set up. The identifier can\n  later be used to retrieve the dual value or subproblem cost function\n  term associated with the constraint.\n  </P> "), see_also : [(>=) / 2, (=:=) / 2, (=<) / 2, $>= / 2, $= / 2, $=< / 2, get / 2]]).
:- comment(minimize / 3, [template : "ColgenInstance:minimize(+SolveSubProblem, +Obj, -ObjVal)", args : ["SolveSubProblem" : "Subproblem solution predicate", "Obj" : "The objective function to minimize", "ObjVal" : "The optimal solution cost"], summary : "Minimizes the problem associated with the colgen instance ColgenInstance.", desc : html("  <P>\n  Minimize the partial linear expression <TT>Obj</TT> for the problem\n  associated with the colgen instance <TT>ColgenInstance</TT>, using\n  the user-defined predicate <TT>SolveSubProblem</TT> to provide\n  profitable variables during solution. The optimal solution cost is\n  unified with <TT>ObjVal</TT>.\n  </P><P>\n  The first argument of the subproblem solution predicate must be a\n  subproblem structure:\n <PRE>\n      sp_prob(master_pool, cutoff, cost, coeff_vars, aux, module)\n </PRE>\n  where and <TT>master_pool</TT> will be unified with the colgen\n  instance <TT>ColgenInstance</TT> so that solutions can be posted to\n  it from within the solution predicate, <TT>cutoff</TT> is a minimum\n  acceptable value for the cost of subproblem solutions that will be\n  updated before calling the predicate, <TT>cost</TT> is the variable\n  occurring in the implicit sum term of <TT>obj</TT> (if any)\n  representing the contribution of new subproblem solutions to the\n  master problem solution cost, <TT>coeff_vars</TT> is a list of all\n  subproblem variables occurring in the implicit sum terms of master\n  problem constraints, and <TT>module</TT> is the module in which the\n  solution predicate should be called.\n  </P>\n  ")]).
:- comment(var_get / 3, [template : "ColgenInstance:var_get(+Var, ++What, -Value)", args : ["Var" : "A solver problem variable for the solver associated with ColgenInstance", "What" : "Specification for information wanted (atom)", "Value" : "Returned value of What"], summary : "Obtain information for an individual solver problem variable Var.", desc : html("<P>\n   Retrieve information about solver constraints and results related to a\n   particular variable, for the colgen instance ColgenInstance.\n   What can take one of the following values:\n<DL>\n    <DT><TT>mp_val</TT>\n    <DD>Returns the floating-point solution for variable Var.\n<P>\n    <DT><TT>cost</TT>\n    <DD>Returns the master problem objective coefficient\n    associated with the variable Var.\n<P>\n    <DT><TT>coeffs</TT>\n    <DD>Returns a list of Id-Val pairs representing the constraint\n    identifiers and coefficient values for the master problem\n    constraints in which the coefficient is non-zero associated\n    with the variable Var.\n<P>\n    <DT><TT>aux</TT>\n    <DD>Returns the auxiliary information associated with the\n    variable Var. The intended use is for subproblem information\n    not represented in the master problem constraint coefficients.\n</DL>")]).